#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>

using namespace std;

//606. 根据二叉树创建字符串
//https://leetcode.cn/problems/construct-string-from-binary-tree/


  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode()
      : val(0)
      , left(nullptr)
      , right(nullptr) {}
      TreeNode(int x)
      : val(x)
      , left(nullptr)
      , right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x)
      , left(left)
      , right(right) {}
  };


/*
class Solution {
public:
    string tree2str(TreeNode* root) {
        if (root == nullptr)
            return "";
        string str = to_string(root->val);
        if (root->left || root->right){
            str += '(';
            str += tree2str(root->left);
            str += ')';
        }
        if (root->right){
            str += '(';
            str += tree2str(root->right);
            str += ')';
        }
        return str;
    }
};
*/

//102. 二叉树的层序遍历
//https://leetcode.cn/problems/binary-tree-level-order-traversal/

/*
class Solution {
public:
    static vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        int levelSize = 0;
        if (root){
            q.push(root);
            levelSize = 1;
        }
        vector<vector<int>> vv;
        while (!q.empty()){
            vector<int> v;
            while (levelSize--){
                TreeNode* front = q.front();
                q.pop();
                v.push_back(front->val);
                if (front->left)
                    q.push(front->left);
                if (front->right)
                    q.push(front->right);
            }
            vv.push_back(v);
            levelSize = q.size();
        }
        return vv;
    }
};

void  test1(){
    TreeNode* root3 = new TreeNode(3);
    TreeNode* root9 = new TreeNode(9);
    TreeNode* root20 = new TreeNode(20);
    TreeNode* root15 = new TreeNode(15);
    TreeNode* root7 = new TreeNode(7);
    root3->left = root9;
    root3->right = root20;
    root20->left = root15;
    root20->right = root7;
    root7->right = new TreeNode(66);
    vector<vector<int>> ret = Solution::levelOrder(root3);
    for (auto e : ret) {
        for (int i : e) {
            cout << i << " ";
        }
        cout << endl;
    }
}
*/

//236. 二叉树的最近公共祖先
//https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

/*
class Solution {
public:
    static bool IsInTree(TreeNode* root, TreeNode* x){
        if (root == nullptr)
            return false;
        return root == x || IsInTree(root->left, x) || IsInTree(root->right, x);
    }

    static TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (p == root || q == root)
            return root;

        bool pInLeft = IsInTree(root->left, p);
        bool pInRight = !pInLeft;
        bool qInLeft = IsInTree(root->left, q);
        bool qInRight = !qInLeft;

        if ((pInLeft && qInRight) || (pInRight && qInLeft))
            return root;
        else if (pInLeft && qInLeft)
            return lowestCommonAncestor(root->left, p, q);
        else
            return lowestCommonAncestor(root->right, p, q);
    }
};
*/

/*
class Solution {
public:
    bool GetPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& Path){
        if (root == nullptr)
            return false;

        Path.push(root);
        if (root == x)
            return true;
        if (GetPath(root->left, x, Path))
            return true;
        if (GetPath(root->right, x, Path))
            return true;

        Path.pop();
        return false;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> pPath, qPath;
        GetPath(root, p, pPath);
        GetPath(root, q, qPath);

        while (pPath.size() != qPath.size()){
            if (pPath.size() > qPath.size())
                pPath.pop();
            else
                qPath.pop();
        }

        while (pPath.top() != qPath.top()){
            pPath.pop();
            qPath.pop();
        }
        return pPath.top();
    }
};
*/

//JZ36 二叉搜索树与双向链表
//https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&&tqId=11179&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

/*
class Solution {
public:
    void InOrderConvert(TreeNode* cur, TreeNode*& prev){
        if (cur == nullptr)
            return;

        InOrderConvert(cur->left, prev);

        cur->left = prev;
        if (prev)
            prev->right = cur;
        prev = cur;

        InOrderConvert(cur->right, prev);
    }

    TreeNode* Convert(TreeNode* pRootOfTree) {
        TreeNode* prev = nullptr;
        InOrderConvert(pRootOfTree, prev);

        TreeNode* head = pRootOfTree;
        while (head && head->left)
            head = head->left;
        return head;
    }
};

void  test1(){
    TreeNode* root10 = new TreeNode(10);
    TreeNode* root6 = new TreeNode(6);
    TreeNode* root14 = new TreeNode(14);
    TreeNode* root4 = new TreeNode(4);
    TreeNode* root8 = new TreeNode(8);
    root10->left = root6;
    root10->right = root14;
    root6->left = root4;
    root6->right = root8;
    Solution().Convert(root10);
}
*/

//105. 从前序与中序遍历序列构造二叉树
//https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

/*
class Solution {
public:
    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& preI, int inBegin, int inEnd){
        if (inBegin > inEnd)
            return nullptr;
        //创建新节点
        auto* root = new TreeNode(preorder[preI]);

        //分割出左右子区间
        int rootI = inBegin;
        while (rootI <= inEnd){
            if (inorder[rootI] == preorder[preI])
                break;
            else
                ++rootI;
        }
        ++preI;
        root->left = _buildTree(preorder, inorder, preI, inBegin, rootI - 1);
        root->right = _buildTree(preorder, inorder, preI, rootI + 1, inEnd);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;
        return _buildTree(preorder, inorder, i, 0, inorder.size() - 1);
    }
};
*/

//106. 从中序与后序遍历序列构造二叉树
//https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

/*
class Solution {
public:
    TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int& postI, int inBegin, int inEnd){
        if (inBegin > inEnd)
            return nullptr;
        auto* root = new TreeNode(postorder[postI]);

        int rootI = inBegin;
        while (rootI <= inEnd){
            if (inorder[rootI] == postorder[postI])
                break;
            else
                ++rootI;
        }
        --postI;
        root->right = _buildTree(inorder, postorder, postI, rootI + 1, inEnd);
        root->left = _buildTree(inorder, postorder, postI, inBegin, rootI - 1);
        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int i = postorder.size() - 1;
        return _buildTree(inorder, postorder, i, 0, inorder.size() - 1);
    }
};

void test1(){
    int a1[] = {9,3,15,20,7};
    int a2[] = {9,15,7,20,3};
    vector<int> inorder(a1,a1 + 5), postorder(a2,a2 + 5);
    TreeNode* root = Solution().buildTree(inorder, postorder);
}
*/

//144. 二叉树的前序遍历
//https://leetcode.cn/problems/binary-tree-preorder-traversal/

/*
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        vector<int>  v;
        while (cur || !st.empty()){
            //开始访问一棵树
            //左路节点
            while (cur){
               v.push_back(cur->val);
               st.push(cur);
               cur = cur->left;
            }
            //右子树
            TreeNode* top = st.top();
            st.pop();
            //子问题访问右子树
            cur = top->right;
        }
        return v;
    }
};
*/

//94. 二叉树的中序遍历
//https://leetcode.cn/problems/binary-tree-inorder-traversal/

/*
class Solution {
public:
    static vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        vector<int> v;
        while (cur || !st.empty()){
            while (cur){
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* top = st.top();
            st.pop();
            v.push_back(top->val);
            cur = top->right;
        }
        return v;
    }
};

void  test1(){
    auto* root10 = new TreeNode(10);
    auto* root6 = new TreeNode(6);
    auto* root1 = new TreeNode(1);
    auto* root4 = new TreeNode(4);
    auto* root8 = new TreeNode(8);
    auto* root3 = new TreeNode(3);
    auto* root7 = new TreeNode(7);
    root8->left = root3;
    root8->right = root10;
    root3->left = root1;
    root3->right = root6;
    root6->left = root4;
    root6->right = root7;
    vector<int> v = Solution::inorderTraversal(root8);
    for (int i : v) {
        cout << i << " ";
    }
    cout << endl;
}
*/

//145. 二叉树的后序遍历
//https://leetcode.cn/problems/binary-tree-postorder-traversal/

/*class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {

    }
};*/

//法1:后序即'左右根'，利用前序的'根左右'改为'根右左'，再逆序即可
/*
class Solution {
public:
    static vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        vector<int>  v;
        while (cur || !st.empty()){
            //开始访问一棵树
            //右路节点
            while (cur){
                v.push_back(cur->val);
                st.push(cur);
                cur = cur->right;
            }
            //右子树
            TreeNode* top = st.top();
            st.pop();
            //子问题访问右子树
            cur = top->left;
        }
        reverse(v.begin(), v.end());
        return v;
    }
};

void  test1(){
    auto* root10 = new TreeNode(10);
    auto* root6 = new TreeNode(6);
    auto* root1 = new TreeNode(1);
    auto* root4 = new TreeNode(4);
    auto* root8 = new TreeNode(8);
    auto* root3 = new TreeNode(3);
    auto* root7 = new TreeNode(7);
    root8->left = root3;
    root8->right = root10;
    root3->left = root1;
    root3->right = root6;
    root6->left = root4;
    root6->right = root7;
    vector<int> v = Solution::postorderTraversal(root8);
    for (int i : v) {
        cout << i << " ";
    }
    cout << endl;
}
*/

/*
class Solution {
public:
    static vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        vector<int>  v;
        TreeNode* prev = nullptr;
        while (cur || !st.empty()){
            while (cur){
                st.push(cur);
                cur = cur->left;
            }
            //右子树
            TreeNode* top = st.top();
            if (top->right == nullptr || top->right == prev){
                v.push_back(top->val);
                st.pop();
                prev = top;
            } else
                cur = top->right;
        }
        return v;
    }
};

void  test1(){
    auto* root10 = new TreeNode(10);
    auto* root6 = new TreeNode(6);
    auto* root1 = new TreeNode(1);
    auto* root4 = new TreeNode(4);
    auto* root8 = new TreeNode(8);
    auto* root3 = new TreeNode(3);
    auto* root7 = new TreeNode(7);
    root8->left = root3;
    root8->right = root10;
    root3->left = root1;
    root3->right = root6;
    root6->left = root4;
    root6->right = root7;
    vector<int> v = Solution::postorderTraversal(root8);
    for (int i : v) {
        cout << i << " ";
    }
    cout << endl;
}
*/

//剑指 Offer 35. 复杂链表的复制
//https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof/

class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

class Solution {
public:
    static Node* copyRandomList(Node* head) {
        map<Node*, Node*> originalCopyMap;
        Node* cur = head;
        Node* copyHead, *copyTail;
        copyHead = copyTail = nullptr;
        while (cur){
            Node* copy = new Node(cur->val);
            originalCopyMap[cur] = copy;
            if (copyTail == nullptr)
                copyTail = copyHead = copy;
            else
            {
                copyTail->next = copy;
                copyTail = copyTail->next;
            }
            cur = cur->next;
        }
        cur = head;
        Node* copy = copyHead;
        while (cur){
            if (cur->random == nullptr)
                copy->random = nullptr;
            else
                copy->random = originalCopyMap[cur->random];
            cur = cur->next;
            copy = copy->next;
        }
        return copyHead;
    }
};

int main() {
    //test1();
    return 0;
}
